home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / dejagnu.lha / dejagnu-1.0.1 / expect / exp_regexp.c < prev    next >
C/C++ Source or Header  |  1993-04-15  |  28KB  |  1,230 lines
  1. /*
  2.  * regcomp and regexec -- regsub and regerror are elsewhere
  3.  *
  4.  *    Copyright (c) 1986 by University of Toronto.
  5.  *    Written by Henry Spencer.  Not derived from licensed software.
  6.  *
  7.  *    Permission is granted to anyone to use this software for any
  8.  *    purpose on any computer system, and to redistribute it freely,
  9.  *    subject to the following restrictions:
  10.  *
  11.  *    1. The author is not responsible for the consequences of use of
  12.  *        this software, no matter how awful, even if they arise
  13.  *        from defects in it.
  14.  *
  15.  *    2. The origin of this software must not be misrepresented, either
  16.  *        by explicit claim or by omission.
  17.  *
  18.  *    3. Altered versions must be plainly marked as such, and must not
  19.  *        be misrepresented as being the original software.
  20.  *
  21.  * Beware that some of this code is subtly aware of the way operator
  22.  * precedence is structured in regular expressions.  Serious changes in
  23.  * regular-expression syntax might require a total rethink.
  24.  *
  25.  * *** NOTE: this code has been altered slightly for use in Tcl. ***
  26.  * *** The only change is to use ckalloc and ckfree instead of   ***
  27.  * *** malloc and free.                         ***
  28.  
  29.  * *** and again for Expect!!! - DEL
  30.  
  31.  */
  32.  
  33. #include "exp_conf.h"
  34. #include "regexp.h"
  35. #include "exp_global.h"
  36. #include "exp_regexp.h"
  37.  
  38. #define NOTSTATIC    /* was at one time, but Expect needs access */
  39.  
  40. /*
  41.  * The "internal use only" fields in regexp.h are present to pass info from
  42.  * compile to execute that permits the execute phase to run lots faster on
  43.  * simple cases.  They are:
  44.  *
  45.  * regstart    char that must begin a match; '\0' if none obvious
  46.  * reganch    is the match anchored (at beginning-of-line only)?
  47.  * regmust    string (pointer into program) that match must include, or NULL
  48.  * regmlen    length of regmust string
  49.  *
  50.  * Regstart and reganch permit very fast decisions on suitable starting points
  51.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  52.  * of lines that cannot possibly match.  The regmust tests are costly enough
  53.  * that regcomp() supplies a regmust only if the r.e. contains something
  54.  * potentially expensive (at present, the only such thing detected is * or +
  55.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  56.  * supplied because the test in regexec() needs it and regcomp() is computing
  57.  * it anyway.
  58.  */
  59.  
  60. /*
  61.  * Structure for regexp "program".  This is essentially a linear encoding
  62.  * of a nondeterministic finite-state machine (aka syntax charts or
  63.  * "railroad normal form" in parsing technology).  Each node is an opcode
  64.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  65.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  66.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  67.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  68.  * opposed to a collection of them) is never concatenated with anything
  69.  * because of operator precedence.)  The operand of some types of node is
  70.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  71.  * particular, the operand of a BRANCH node is the first node of the branch.
  72.  * (NB this is *not* a tree structure:  the tail of the branch connects
  73.  * to the thing following the set of BRANCHes.)  The opcodes are:
  74.  */
  75.  
  76. /* definition    number    opnd?    meaning */
  77. #define    END    0    /* no    End of program. */
  78. #define    BOL    1    /* no    Match "" at beginning of line. */
  79. #define    EOL    2    /* no    Match "" at end of line. */
  80. #define    ANY    3    /* no    Match any one character. */
  81. #define    ANYOF    4    /* str    Match any character in this string. */
  82. #define    ANYBUT    5    /* str    Match any character not in this string. */
  83. #define    BRANCH    6    /* node    Match this alternative, or the next... */
  84. #define    BACK    7    /* no    Match "", "next" ptr points backward. */
  85. #define    EXACTLY    8    /* str    Match this string. */
  86. #define    NOTHING    9    /* no    Match empty string. */
  87. #define    STAR    10    /* node    Match this (simple) thing 0 or more times. */
  88. #define    PLUS    11    /* node    Match this (simple) thing 1 or more times. */
  89. #define    OPEN    20    /* no    Mark this point in input as start of #n. */
  90.             /*    OPEN+1 is number 1, etc. */
  91. #define    CLOSE    30    /* no    Analogous to OPEN. */
  92.  
  93. /*
  94.  * Opcode notes:
  95.  *
  96.  * BRANCH    The set of branches constituting a single choice are hooked
  97.  *        together with their "next" pointers, since precedence prevents
  98.  *        anything being concatenated to any individual branch.  The
  99.  *        "next" pointer of the last BRANCH in a choice points to the
  100.  *        thing following the whole choice.  This is also where the
  101.  *        final "next" pointer of each individual branch points; each
  102.  *        branch starts with the operand node of a BRANCH node.
  103.  *
  104.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  105.  *        exists to make loop structures possible.
  106.  *
  107.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  108.  *        BRANCH structures using BACK.  Simple cases (one character
  109.  *        per match) are implemented with STAR and PLUS for speed
  110.  *        and to minimize recursive plunges.
  111.  *
  112.  * OPEN,CLOSE    ...are numbered at compile time.
  113.  */
  114.  
  115. /*
  116.  * A node is one char of opcode followed by two chars of "next" pointer.
  117.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  118.  * value is a positive offset from the opcode of the node containing it.
  119.  * An operand, if any, simply follows the node.  (Note that much of the
  120.  * code generation knows about this implicit relationship.)
  121.  *
  122.  * Using two bytes for the "next" pointer is vast overkill for most things,
  123.  * but allows patterns to get big without disasters.
  124.  */
  125. #define    OP(p)    (*(p))
  126. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  127. #define    OPERAND(p)    ((p) + 3)
  128.  
  129. /*
  130.  * See regmagic.h for one further detail of program structure.
  131.  */
  132.  
  133.  
  134. /*
  135.  * Utility definitions.
  136.  */
  137. #ifndef CHARBITS
  138. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  139. #else
  140. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  141. #endif
  142.  
  143. #define    FAIL(m)    { regerror(m); return(NULL); }
  144. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  145. #define    META    "^$.[()|?+*\\"
  146.  
  147. /*
  148.  * Flags to be passed up and down.
  149.  */
  150. #define    HASWIDTH    01    /* Known never to match null string. */
  151. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  152. #define    SPSTART        04    /* Starts with * or +. */
  153. #define    WORST        0    /* Worst case. */
  154.  
  155. /*
  156.  * Global work variables for regcomp().
  157.  */
  158. static char *regparse;        /* Input-scan pointer. */
  159. static int regnpar;        /* () count. */
  160. static char regdummy;
  161. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  162. static long regsize;        /* Code size. */
  163.  
  164. /*
  165.  * The first byte of the regexp internal "program" is actually this magic
  166.  * number; the start node begins in the second byte.
  167.  */
  168. #define    MAGIC    0234
  169.  
  170.  
  171. /*
  172.  * Forward declarations for regcomp()'s friends.
  173.  */
  174. #ifndef STATIC
  175. #define    STATIC    static
  176. #endif
  177. STATIC char *reg();
  178. STATIC char *regbranch();
  179. STATIC char *regpiece();
  180. STATIC char *regatom();
  181. STATIC char *regnode();
  182. STATIC char *regnext();
  183. STATIC void regc();
  184. STATIC void reginsert();
  185. STATIC void regtail();
  186. STATIC void regoptail();
  187. #ifdef STRCSPN
  188. STATIC int strcspn();
  189. #endif
  190.  
  191. /* regcomp originally appeared here - DEL */
  192.  
  193. /*
  194.  - reg - regular expression, i.e. main body or parenthesized thing
  195.  *
  196.  * Caller must absorb opening parenthesis.
  197.  *
  198.  * Combining parenthesis handling with the base level of regular expression
  199.  * is a trifle forced, but the need to tie the tails of the branches to what
  200.  * follows makes it hard to avoid.
  201.  */
  202. static char *
  203. reg(paren, flagp)
  204. int paren;            /* Parenthesized? */
  205. int *flagp;
  206. {
  207.     register char *ret;
  208.     register char *br;
  209.     register char *ender;
  210.     register int parno = 0;
  211.     int flags;
  212.  
  213.     *flagp = HASWIDTH;    /* Tentatively. */
  214.  
  215.     /* Make an OPEN node, if parenthesized. */
  216.     if (paren) {
  217.         if (regnpar >= NSUBEXP)
  218.             FAIL("too many ()");
  219.         parno = regnpar;
  220.         regnpar++;
  221.         ret = regnode(OPEN+parno);
  222.     } else
  223.         ret = NULL;
  224.  
  225.     /* Pick up the branches, linking them together. */
  226.     br = regbranch(&flags);
  227.     if (br == NULL)
  228.         return(NULL);
  229.     if (ret != NULL)
  230.         regtail(ret, br);    /* OPEN -> first. */
  231.     else
  232.         ret = br;
  233.     if (!(flags&HASWIDTH))
  234.         *flagp &= ~HASWIDTH;
  235.     *flagp |= flags&SPSTART;
  236.     while (*regparse == '|') {
  237.         regparse++;
  238.         br = regbranch(&flags);
  239.         if (br == NULL)
  240.             return(NULL);
  241.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  242.         if (!(flags&HASWIDTH))
  243.             *flagp &= ~HASWIDTH;
  244.         *flagp |= flags&SPSTART;
  245.     }
  246.  
  247.     /* Make a closing node, and hook it on the end. */
  248.     ender = regnode((paren) ? CLOSE+parno : END);    
  249.     regtail(ret, ender);
  250.  
  251.     /* Hook the tails of the branches to the closing node. */
  252.     for (br = ret; br != NULL; br = regnext(br))
  253.         regoptail(br, ender);
  254.  
  255.     /* Check for proper termination. */
  256.     if (paren && *regparse++ != ')') {
  257.         FAIL("unmatched ()");
  258.     } else if (!paren && *regparse != '\0') {
  259.         if (*regparse == ')') {
  260.             FAIL("unmatched ()");
  261.         } else
  262.             FAIL("junk on end");    /* "Can't happen". */
  263.         /* NOTREACHED */
  264.     }
  265.  
  266.     return(ret);
  267. }
  268.  
  269. /*
  270.  - regbranch - one alternative of an | operator
  271.  *
  272.  * Implements the concatenation operator.
  273.  */
  274. static char *
  275. regbranch(flagp)
  276. int *flagp;
  277. {
  278.     register char *ret;
  279.     register char *chain;
  280.     register char *latest;
  281.     int flags;
  282.  
  283.     *flagp = WORST;        /* Tentatively. */
  284.  
  285.     ret = regnode(BRANCH);
  286.     chain = NULL;
  287.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  288.         latest = regpiece(&flags);
  289.         if (latest == NULL)
  290.             return(NULL);
  291.         *flagp |= flags&HASWIDTH;
  292.         if (chain == NULL)    /* First piece. */
  293.             *flagp |= flags&SPSTART;
  294.         else
  295.             regtail(chain, latest);
  296.         chain = latest;
  297.     }
  298.     if (chain == NULL)    /* Loop ran zero times. */
  299.         (void) regnode(NOTHING);
  300.  
  301.     return(ret);
  302. }
  303.  
  304. /*
  305.  - regpiece - something followed by possible [*+?]
  306.  *
  307.  * Note that the branching code sequences used for ? and the general cases
  308.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  309.  * both the endmarker for their branch list and the body of the last branch.
  310.  * It might seem that this node could be dispensed with entirely, but the
  311.  * endmarker role is not redundant.
  312.  */
  313. static char *
  314. regpiece(flagp)
  315. int *flagp;
  316. {
  317.     register char *ret;
  318.     register char op;
  319.     register char *next;
  320.     int flags;
  321.  
  322.     ret = regatom(&flags);
  323.     if (ret == NULL)
  324.         return(NULL);
  325.  
  326.     op = *regparse;
  327.     if (!ISMULT(op)) {
  328.         *flagp = flags;
  329.         return(ret);
  330.     }
  331.  
  332.     if (!(flags&HASWIDTH) && op != '?')
  333.         FAIL("*+ operand could be empty");
  334.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  335.  
  336.     if (op == '*' && (flags&SIMPLE))
  337.         reginsert(STAR, ret);
  338.     else if (op == '*') {
  339.         /* Emit x* as (x&|), where & means "self". */
  340.         reginsert(BRANCH, ret);            /* Either x */
  341.         regoptail(ret, regnode(BACK));        /* and loop */
  342.         regoptail(ret, ret);            /* back */
  343.         regtail(ret, regnode(BRANCH));        /* or */
  344.         regtail(ret, regnode(NOTHING));        /* null. */
  345.     } else if (op == '+' && (flags&SIMPLE))
  346.         reginsert(PLUS, ret);
  347.     else if (op == '+') {
  348.         /* Emit x+ as x(&|), where & means "self". */
  349.         next = regnode(BRANCH);            /* Either */
  350.         regtail(ret, next);
  351.         regtail(regnode(BACK), ret);        /* loop back */
  352.         regtail(next, regnode(BRANCH));        /* or */
  353.         regtail(ret, regnode(NOTHING));        /* null. */
  354.     } else if (op == '?') {
  355.         /* Emit x? as (x|) */
  356.         reginsert(BRANCH, ret);            /* Either x */
  357.         regtail(ret, regnode(BRANCH));        /* or */
  358.         next = regnode(NOTHING);        /* null. */
  359.         regtail(ret, next);
  360.         regoptail(ret, next);
  361.     }
  362.     regparse++;
  363.     if (ISMULT(*regparse))
  364.         FAIL("nested *?+");
  365.  
  366.     return(ret);
  367. }
  368.  
  369. /*
  370.  - regatom - the lowest level
  371.  *
  372.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  373.  * it can turn them into a single node, which is smaller to store and
  374.  * faster to run.  Backslashed characters are exceptions, each becoming a
  375.  * separate node; the code is simpler that way and it's not worth fixing.
  376.  */
  377. static char *
  378. regatom(flagp)
  379. int *flagp;
  380. {
  381.     register char *ret;
  382.     int flags;
  383.  
  384.     *flagp = WORST;        /* Tentatively. */
  385.  
  386.     switch (*regparse++) {
  387.     case '^':
  388.         ret = regnode(BOL);
  389.         break;
  390.     case '$':
  391.         ret = regnode(EOL);
  392.         break;
  393.     case '.':
  394.         ret = regnode(ANY);
  395.         *flagp |= HASWIDTH|SIMPLE;
  396.         break;
  397.     case '[': {
  398.             register int clss;
  399.             register int classend;
  400.  
  401.             if (*regparse == '^') {    /* Complement of range. */
  402.                 ret = regnode(ANYBUT);
  403.                 regparse++;
  404.             } else
  405.                 ret = regnode(ANYOF);
  406.             if (*regparse == ']' || *regparse == '-')
  407.                 regc(*regparse++);
  408.             while (*regparse != '\0' && *regparse != ']') {
  409.                 if (*regparse == '-') {
  410.                     regparse++;
  411.                     if (*regparse == ']' || *regparse == '\0')
  412.                         regc('-');
  413.                     else {
  414.                         clss = UCHARAT(regparse-2)+1;
  415.                         classend = UCHARAT(regparse);
  416.                         if (clss > classend+1)
  417.                             FAIL("invalid [] range");
  418.                         for (; clss <= classend; clss++)
  419.                             regc(clss);
  420.                         regparse++;
  421.                     }
  422.                 } else
  423.                     regc(*regparse++);
  424.             }
  425.             regc('\0');
  426.             if (*regparse != ']')
  427.                 FAIL("unmatched []");
  428.             regparse++;
  429.             *flagp |= HASWIDTH|SIMPLE;
  430.         }
  431.         break;
  432.     case '(':
  433.         ret = reg(1, &flags);
  434.         if (ret == NULL)
  435.             return(NULL);
  436.         *flagp |= flags&(HASWIDTH|SPSTART);
  437.         break;
  438.     case '\0':
  439.     case '|':
  440.     case ')':
  441.         FAIL("internal urp");    /* Supposed to be caught earlier. */
  442.         /* NOTREACHED */
  443.         break;
  444.     case '?':
  445.     case '+':
  446.     case '*':
  447.         FAIL("?+* follows nothing");
  448.         /* NOTREACHED */
  449.         break;
  450.     case '\\':
  451.         if (*regparse == '\0')
  452.             FAIL("trailing \\");
  453.         ret = regnode(EXACTLY);
  454.         regc(*regparse++);
  455.         regc('\0');
  456.         *flagp |= HASWIDTH|SIMPLE;
  457.         break;
  458.     default: {
  459.             register int len;
  460.             register char ender;
  461.  
  462.             regparse--;
  463.             len = strcspn(regparse, META);
  464.             if (len <= 0)
  465.                 FAIL("internal disaster");
  466.             ender = *(regparse+len);
  467.             if (len > 1 && ISMULT(ender))
  468.                 len--;        /* Back off clear of ?+* operand. */
  469.             *flagp |= HASWIDTH;
  470.             if (len == 1)
  471.                 *flagp |= SIMPLE;
  472.             ret = regnode(EXACTLY);
  473.             while (len > 0) {
  474.                 regc(*regparse++);
  475.                 len--;
  476.             }
  477.             regc('\0');
  478.         }
  479.         break;
  480.     }
  481.  
  482.     return(ret);
  483. }
  484.  
  485. /*
  486.  - regnode - emit a node
  487.  */
  488. static char *            /* Location. */
  489. regnode(op)
  490. char op;
  491. {
  492.     register char *ret;
  493.     register char *ptr;
  494.  
  495.     ret = regcode;
  496.     if (ret == ®dummy) {
  497.         regsize += 3;
  498.         return(ret);
  499.     }
  500.  
  501.     ptr = ret;
  502.     *ptr++ = op;
  503.     *ptr++ = '\0';        /* Null "next" pointer. */
  504.     *ptr++ = '\0';
  505.     regcode = ptr;
  506.  
  507.     return(ret);
  508. }
  509.  
  510. /*
  511.  - regc - emit (if appropriate) a byte of code
  512.  */
  513. static void
  514. regc(b)
  515. char b;
  516. {
  517.     if (regcode != ®dummy)
  518.         *regcode++ = b;
  519.     else
  520.         regsize++;
  521. }
  522.  
  523. /*
  524.  - reginsert - insert an operator in front of already-emitted operand
  525.  *
  526.  * Means relocating the operand.
  527.  */
  528. static void
  529. reginsert(op, opnd)
  530. char op;
  531. char *opnd;
  532. {
  533.     register char *src;
  534.     register char *dst;
  535.     register char *place;
  536.  
  537.     if (regcode == ®dummy) {
  538.         regsize += 3;
  539.         return;
  540.     }
  541.  
  542.     src = regcode;
  543.     regcode += 3;
  544.     dst = regcode;
  545.     while (src > opnd)
  546.         *--dst = *--src;
  547.  
  548.     place = opnd;        /* Op node, where operand used to be. */
  549.     *place++ = op;
  550.     *place++ = '\0';
  551.     *place++ = '\0';
  552. }
  553.  
  554. /*
  555.  - regtail - set the next-pointer at the end of a node chain
  556.  */
  557. static void
  558. regtail(p, val)
  559. char *p;
  560. char *val;
  561. {
  562.     register char *scan;
  563.     register char *temp;
  564.     register int offset;
  565.  
  566.     if (p == ®dummy)
  567.         return;
  568.  
  569.     /* Find last node. */
  570.     scan = p;
  571.     for (;;) {
  572.         temp = regnext(scan);
  573.         if (temp == NULL)
  574.             break;
  575.         scan = temp;
  576.     }
  577.  
  578.     if (OP(scan) == BACK)
  579.         offset = scan - val;
  580.     else
  581.         offset = val - scan;
  582.     *(scan+1) = (offset>>8)&0377;
  583.     *(scan+2) = offset&0377;
  584. }
  585.  
  586. /*
  587.  - regoptail - regtail on operand of first argument; nop if operandless
  588.  */
  589. static void
  590. regoptail(p, val)
  591. char *p;
  592. char *val;
  593. {
  594.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  595.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  596.         return;
  597.     regtail(OPERAND(p), val);
  598. }
  599.  
  600. /*
  601.  * regexec and friends
  602.  */
  603.  
  604. /*
  605.  * Global work variables for regexec().
  606.  */
  607. static char *reginput;        /* String-input pointer. */
  608. NOTSTATIC char *regbol;        /* Beginning of input, for ^ check. */
  609. static char **regstartp;    /* Pointer to startp array. */
  610. static char **regendp;        /* Ditto for endp. */
  611.  
  612. /*
  613.  * Forwards.
  614.  */
  615.  
  616. NOTSTATIC int regtry();
  617. STATIC int regmatch();
  618. STATIC int regrepeat();
  619.  
  620. #ifdef DEBUG
  621. int regnarrate = 0;
  622. void regdump();
  623. STATIC char *regprop();
  624. #endif
  625.  
  626. #if 0
  627. /*
  628.  - regexec - match a regexp against a string
  629.  */
  630. int
  631. regexec(prog, string, stringlength, matchlength)
  632. register regexp *prog;
  633. register char *string;    /* note: CURRENTLY ASSUMED TO BE NULL-TERMINATED!!! */
  634. int stringlength;    /* length of string */
  635. int *matchlength;    /* number of chars matched (or to be skipped) */
  636.             /* set when MATCH or CANT_MATCH */
  637. {
  638.     register char *s;
  639.     extern char *strchr();
  640.  
  641.     /* Be paranoid... */
  642.     if (prog == NULL || string == NULL) {
  643.         regerror("NULL parameter");
  644.         return(EXP_TCLERROR);
  645.     }
  646.  
  647.     /* Check validity of program. */
  648.     if (UCHARAT(prog->program) != MAGIC) {
  649.         regerror("corrupted program");
  650.         return(EXP_KM_ERROR);
  651.     }
  652.  
  653. #if THIS_RUINS_EXP
  654. /* no need for this shortcut anyway */
  655.     /* If there is a "must appear" string, look for it. */
  656.     if (prog->regmust != NULL) {
  657.         s = string;
  658.         while ((s = strchr(s, prog->regmust[0])) != NULL) {
  659.             if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  660.                 break;    /* Found it. */
  661.             s++;
  662.         }
  663.         if (s == NULL)    /* Not present. */
  664.             return(0);
  665.     }
  666. #endif
  667.  
  668.     /* Mark beginning of line for ^ . */
  669.     regbol = string;
  670.  
  671.     /* Simplest case:  anchored match need be tried only once. */
  672.     if (prog->reganch) {
  673.         int r = regtry(prog,string,matchlength);
  674.         if (r == CANT_MATCH) *matchlength = stringlength;
  675.         return(r);
  676.     }
  677.  
  678.     /* Messy cases:  unanchored match. */
  679.     s = string;
  680.     if (prog->regstart != '\0') {
  681.         register char *s2 = s;
  682.  
  683.         /* We know what char it must start with. */
  684.         while (1) {
  685.             int r;
  686.  
  687.             s2 = strchr(s2,prog->regstart);
  688.             if (s2 == 0) {
  689.                 *matchlength = stringlength;
  690.                 return(CANT_MATCH);
  691.             }
  692.             r = regtry(prog,s2,matchlength);
  693.             if (r == CANT_MATCH) {
  694.                 s2++;
  695.                 continue;
  696.             }
  697.             if (s2 == s) return(r);
  698.             *matchlength = s2-s;
  699.             return CANT_MATCH;
  700.         }
  701.     } else {
  702.         /* We don't -- general case. */
  703.         register char *s2 = s;
  704.         int r = regtry(prog,s,matchlength);
  705.         if (r == EXP_MATCH) return(r);
  706.         else if (r == EXP_CANMATCH) return(r);
  707.         /* at this point, we know some characters at front */
  708.         /* of string don't match */
  709.         for (s2++;*s2;s2++) {
  710.             r = regtry(prog,s2,matchlength);
  711.             if (r == CANT_MATCH) continue;
  712.             /* if we match or can_match, say cant_match and */
  713.             /* record the number of chars at front that don't match */
  714.             *matchlength = s2-s;
  715.             return(CANT_MATCH);
  716.         }
  717.         /* made it thru string with CANT_MATCH all the way */
  718.         *matchlength = stringlength;
  719.         return(CANT_MATCH);
  720.     }
  721. }
  722. #endif
  723.  
  724. /*
  725.  - regtry - try match at specific point
  726.  */
  727. /* return CAN_MATCH, CANT_MATCH or MATCH */
  728. int            /* 0 failure, 1 success */
  729. regtry(prog, string, matchlength)
  730. regexp *prog;
  731. char *string;
  732. int *matchlength;    /* only set for MATCH */
  733. {
  734.     register int i;
  735.     register char **sp;
  736.     register char **ep;
  737.     int r;        /* result of regmatch */
  738.  
  739.     reginput = string;
  740.     regstartp = prog->startp;
  741.     regendp = prog->endp;
  742.  
  743.     sp = prog->startp;
  744.     ep = prog->endp;
  745.     for (i = NSUBEXP; i > 0; i--) {
  746.         *sp++ = NULL;
  747.         *ep++ = NULL;
  748.     }
  749.     r = regmatch(prog->program + 1);
  750.     if (EXP_MATCH == r) {
  751.         prog->startp[0] = string;
  752.         prog->endp[0] = reginput;
  753.         *matchlength = reginput-string;
  754.         return(EXP_MATCH);
  755.     }
  756.     return(r);    /* CAN_MATCH or CANT_MATCH */
  757. }
  758.  
  759. /*
  760.  - regmatch - main matching routine
  761.  *
  762.  * Conceptually the strategy is simple:  check to see whether the current
  763.  * node matches, call self recursively to see whether the rest matches,
  764.  * and then act accordingly.  In practice we make some effort to avoid
  765.  * recursion, in particular by going through "ordinary" nodes (that don't
  766.  * need to know whether the rest of the match failed) by a loop instead of
  767.  * by recursion.
  768.  */
  769. /* returns CAN, CANT or MATCH */
  770. static int            /* 0 failure, 1 success */
  771. regmatch(prog)
  772. char *prog;
  773. {
  774.     register char *scan;    /* Current node. */
  775.     char *next;        /* Next node. */
  776.     extern char *strchr();
  777.  
  778.     scan = prog;
  779. #ifdef DEBUG
  780.     if (scan != NULL && regnarrate)
  781.         fprintf(stderr, "%s(\n", regprop(scan));
  782. #endif
  783.     while (scan != NULL) {
  784. #ifdef DEBUG
  785.         if (regnarrate)
  786.             fprintf(stderr, "%s...\n", regprop(scan));
  787. #endif
  788.         next = regnext(scan);
  789.  
  790.         switch (OP(scan)) {
  791.         case BOL:
  792.             if (reginput != regbol)
  793. /*                return(0);*/
  794.                 /* not exactly sure about this */
  795.                 return(EXP_CANTMATCH);
  796.             break;
  797.         case EOL:
  798.             if (*reginput != '\0')
  799. /*                return(0);*/
  800. /* note this implies that "$" must match everything received to this point! */
  801.                 return(EXP_CANTMATCH);
  802.             break;
  803.         case ANY:
  804.             if (*reginput == '\0')
  805. /*                return(0);*/
  806.                 return(EXP_CANMATCH);
  807.             reginput++;
  808.             break;
  809.         case EXACTLY: {
  810. /*                register int len;*/
  811.                 register char *opnd;
  812.  
  813.                 opnd = OPERAND(scan);
  814.  
  815.                 /* this section of code is totally rewritten - DEL */
  816.                 /* group of literal chars in pattern */
  817.                 /* compare each one */
  818.                 do {
  819.                     if (*opnd != *reginput) {
  820.                         if (*reginput == '\0') {
  821.                             return EXP_CANMATCH;
  822.                         } else     return EXP_CANTMATCH;
  823.                     }
  824.  
  825.                     reginput++;
  826.                     opnd++;
  827.                 } while (*opnd != '\0');
  828.             }
  829.             break;
  830.         case ANYOF:
  831. /*             if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  832.                 return(0);
  833. */
  834.             if (*reginput == '\0')
  835.                 return(EXP_CANMATCH);
  836.             if (strchr(OPERAND(scan),*reginput) == NULL)
  837.                 return(EXP_CANTMATCH);
  838.             reginput++;
  839.             break;
  840.         case ANYBUT:
  841. /*             if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  842.                 return(0);
  843. */
  844.             if (*reginput == '\0')
  845.                 return(EXP_CANMATCH);
  846.             if (strchr(OPERAND(scan),*reginput) != NULL)
  847.                 return(EXP_CANTMATCH);
  848.             reginput++;
  849.             break;
  850.         case NOTHING:
  851.             break;
  852.         case BACK:
  853.             break;
  854.         case OPEN+1:
  855.         case OPEN+2:
  856.         case OPEN+3:
  857.         case OPEN+4:
  858.         case OPEN+5:
  859.         case OPEN+6:
  860.         case OPEN+7:
  861.         case OPEN+8:
  862.         case OPEN+9: {
  863.                 register int no;
  864.                 register char *save;
  865.                 int r;    /* result of regmatch */
  866.  
  867.                 no = OP(scan) - OPEN;
  868.                 save = reginput;
  869.  
  870.                 r = regmatch(next);
  871.                 if (r == EXP_MATCH) {
  872.                     /*
  873.                      * Don't set startp if some later
  874.                      * invocation of the same parentheses
  875.                      * already has.
  876.                      */
  877.                     if (regstartp[no] == NULL)
  878.                         regstartp[no] = save;
  879.                 }
  880.                 return(r);
  881.             }
  882.             /* NOTREACHED */
  883.             break;
  884.         case CLOSE+1:
  885.         case CLOSE+2:
  886.         case CLOSE+3:
  887.         case CLOSE+4:
  888.         case CLOSE+5:
  889.         case CLOSE+6:
  890.         case CLOSE+7:
  891.         case CLOSE+8:
  892.         case CLOSE+9: {
  893.                 register int no;
  894.                 register char *save;
  895.                 int r;    /* result of regmatch */
  896.  
  897.                 no = OP(scan) - CLOSE;
  898.                 save = reginput;
  899.  
  900.                 r = regmatch(next);
  901.                 if (r == EXP_MATCH) {
  902.                     /*
  903.                      * Don't set endp if some later
  904.                      * invocation of the same parentheses
  905.                      * already has.
  906.                      */
  907.                     if (regendp[no] == NULL)
  908.                         regendp[no] = save;
  909.                 }
  910.                 return(r);
  911.             }
  912.             /* NOTREACHED */
  913.             break;
  914.         case BRANCH: {
  915.                 register char *save;
  916.                 int match_status;
  917.  
  918.                 if (OP(next) != BRANCH)        /* No choice. */
  919.                     next = OPERAND(scan);    /* Avoid recursion. */
  920.                 else {
  921.                     match_status = EXP_CANTMATCH;
  922.  
  923.                     do {
  924.                         int r;
  925.  
  926.                         save = reginput;
  927.                         r = regmatch(OPERAND(scan));
  928.                         if (r == EXP_MATCH) return(r);
  929.                         if (r == EXP_CANMATCH) {
  930.                             match_status = r;
  931.                         }
  932.                         reginput = save;
  933.                         scan = regnext(scan);
  934.                     } while (scan != NULL && OP(scan) == BRANCH);
  935.                     return(match_status);
  936.                     /* NOTREACHED */
  937.                 }
  938.             }
  939.             /* NOTREACHED */
  940.             break;
  941.         case STAR:
  942.         case PLUS: {
  943.                 register char nextch;
  944.                 register int no;
  945.                 register char *save;
  946.                 register int min;
  947.                 int match_status;
  948.  
  949.                 /*
  950.                  * Lookahead to avoid useless match attempts
  951.                  * when we know what character comes next.
  952.                  */
  953.                 match_status = EXP_CANTMATCH;
  954.                 nextch = '\0';
  955.                 if (OP(next) == EXACTLY)
  956.                     nextch = *OPERAND(next);
  957.                 min = (OP(scan) == STAR) ? 0 : 1;
  958.                 save = reginput;
  959.                 no = regrepeat(OPERAND(scan));
  960.                 while (no >= min) {
  961.                     /* If it could work, try it. */
  962.                     /* 3rd condition allows for CAN_MATCH */
  963.                     if (nextch == '\0' || *reginput == nextch || *reginput == '\0') {
  964.                         int r = regmatch(next);
  965.                         if (r == EXP_MATCH)
  966.                             return(EXP_MATCH);
  967.                         if (r == EXP_CANMATCH)
  968.                             match_status = r;
  969.                     }
  970.                     /* Couldn't or didn't -- back up. */
  971.                     no--;
  972.                     reginput = save + no;
  973.                 }
  974.                 return(match_status);
  975.             }
  976.             /* NOTREACHED */
  977.             break;
  978.         case END:
  979.             return(EXP_MATCH);    /* Success! */
  980.             /* NOTREACHED */
  981.             break;
  982.         default:
  983.             regerror("memory corruption");
  984.             return(EXP_TCLERROR);
  985.             /* NOTREACHED */
  986.             break;
  987.         }
  988.  
  989.         scan = next;
  990.     }
  991.  
  992.     /*
  993.      * We get here only if there's trouble -- normally "case END" is
  994.      * the terminating point.
  995.      */
  996.     regerror("corrupted pointers");
  997.     return(EXP_TCLERROR);
  998. }
  999.  
  1000. /*
  1001.  - regrepeat - repeatedly match something simple, report how many
  1002.  */
  1003. static int
  1004. regrepeat(p)
  1005. char *p;
  1006. {
  1007.     register int count = 0;
  1008.     register char *scan;
  1009.     register char *opnd;
  1010.  
  1011.     scan = reginput;
  1012.     opnd = OPERAND(p);
  1013.     switch (OP(p)) {
  1014.     case ANY:
  1015.         count = strlen(scan);
  1016.         scan += count;
  1017.         break;
  1018.     case EXACTLY:
  1019.         while (*opnd == *scan) {
  1020.             count++;
  1021.             scan++;
  1022.         }
  1023.         break;
  1024.     case ANYOF:
  1025.         while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1026.             count++;
  1027.             scan++;
  1028.         }
  1029.         break;
  1030.     case ANYBUT:
  1031.         while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1032.             count++;
  1033.             scan++;
  1034.         }
  1035.         break;
  1036.     default:        /* Oh dear.  Called inappropriately. */
  1037.         regerror("internal foulup");
  1038.         count = 0;    /* Best compromise. */
  1039.         break;
  1040.     }
  1041.     reginput = scan;
  1042.  
  1043.     return(count);
  1044. }
  1045.  
  1046. /*
  1047.  - regnext - dig the "next" pointer out of a node
  1048.  */
  1049. static char *
  1050. regnext(p)
  1051. register char *p;
  1052. {
  1053.     register int offset;
  1054.  
  1055.     if (p == ®dummy)
  1056.         return(NULL);
  1057.  
  1058.     offset = NEXT(p);
  1059.     if (offset == 0)
  1060.         return(NULL);
  1061.  
  1062.     if (OP(p) == BACK)
  1063.         return(p-offset);
  1064.     else
  1065.         return(p+offset);
  1066. }
  1067.  
  1068. #ifdef DEBUG
  1069.  
  1070. STATIC char *regprop();
  1071.  
  1072. /*
  1073.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1074.  */
  1075. void
  1076. regdump(r)
  1077. regexp *r;
  1078. {
  1079.     register char *s;
  1080.     register char op = EXACTLY;    /* Arbitrary non-END op. */
  1081.     register char *next;
  1082.     extern char *strchr();
  1083.  
  1084.  
  1085.     s = r->program + 1;
  1086.     while (op != END) {    /* While that wasn't END last time... */
  1087.         op = OP(s);
  1088.         printf("%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1089.         next = regnext(s);
  1090.         if (next == NULL)        /* Next ptr. */
  1091.             printf("(0)");
  1092.         else 
  1093.             printf("(%d)", (s-r->program)+(next-s));
  1094.         s += 3;
  1095.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1096.             /* Literal string, where present. */
  1097.             while (*s != '\0') {
  1098.                 putchar(*s);
  1099.                 s++;
  1100.             }
  1101.             s++;
  1102.         }
  1103.         putchar('\n');
  1104.     }
  1105.  
  1106.     /* Header fields of interest. */
  1107.     if (r->regstart != '\0')
  1108.         printf("start `%c' ", r->regstart);
  1109.     if (r->reganch)
  1110.         printf("anchored ");
  1111.     if (r->regmust != NULL)
  1112.         printf("must have \"%s\"", r->regmust);
  1113.     printf("\n");
  1114. }
  1115.  
  1116. /*
  1117.  - regprop - printable representation of opcode
  1118.  */
  1119. static char *
  1120. regprop(op)
  1121. char *op;
  1122. {
  1123.     register char *p;
  1124.     static char buf[50];
  1125.  
  1126.     (void) strcpy(buf, ":");
  1127.  
  1128.     switch (OP(op)) {
  1129.     case BOL:
  1130.         p = "BOL";
  1131.         break;
  1132.     case EOL:
  1133.         p = "EOL";
  1134.         break;
  1135.     case ANY:
  1136.         p = "ANY";
  1137.         break;
  1138.     case ANYOF:
  1139.         p = "ANYOF";
  1140.         break;
  1141.     case ANYBUT:
  1142.         p = "ANYBUT";
  1143.         break;
  1144.     case BRANCH:
  1145.         p = "BRANCH";
  1146.         break;
  1147.     case EXACTLY:
  1148.         p = "EXACTLY";
  1149.         break;
  1150.     case NOTHING:
  1151.         p = "NOTHING";
  1152.         break;
  1153.     case BACK:
  1154.         p = "BACK";
  1155.         break;
  1156.     case END:
  1157.         p = "END";
  1158.         break;
  1159.     case OPEN+1:
  1160.     case OPEN+2:
  1161.     case OPEN+3:
  1162.     case OPEN+4:
  1163.     case OPEN+5:
  1164.     case OPEN+6:
  1165.     case OPEN+7:
  1166.     case OPEN+8:
  1167.     case OPEN+9:
  1168.         sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1169.         p = NULL;
  1170.         break;
  1171.     case CLOSE+1:
  1172.     case CLOSE+2:
  1173.     case CLOSE+3:
  1174.     case CLOSE+4:
  1175.     case CLOSE+5:
  1176.     case CLOSE+6:
  1177.     case CLOSE+7:
  1178.     case CLOSE+8:
  1179.     case CLOSE+9:
  1180.         sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1181.         p = NULL;
  1182.         break;
  1183.     case STAR:
  1184.         p = "STAR";
  1185.         break;
  1186.     case PLUS:
  1187.         p = "PLUS";
  1188.         break;
  1189.     default:
  1190.         regerror("corrupted opcode");
  1191.         break;
  1192.     }
  1193.     if (p != NULL)
  1194.         (void) strcat(buf, p);
  1195.     return(buf);
  1196. }
  1197. #endif
  1198.  
  1199. /*
  1200.  * The following is provided for those people who do not have strcspn() in
  1201.  * their C libraries.  They should get off their butts and do something
  1202.  * about it; at least one public-domain implementation of those (highly
  1203.  * useful) string routines has been published on Usenet.
  1204.  */
  1205. #ifdef STRCSPN
  1206. /*
  1207.  * strcspn - find length of initial segment of s1 consisting entirely
  1208.  * of characters not from s2
  1209.  */
  1210.  
  1211. static int
  1212. strcspn(s1, s2)
  1213. char *s1;
  1214. char *s2;
  1215. {
  1216.     register char *scan1;
  1217.     register char *scan2;
  1218.     register int count;
  1219.  
  1220.     count = 0;
  1221.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1222.         for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1223.             if (*scan1 == *scan2++)
  1224.                 return(count);
  1225.         count++;
  1226.     }
  1227.     return(count);
  1228. }
  1229. #endif
  1230.